package week07

// 686. 重复叠加字符串匹配
// https://leetcode-cn.com/problems/repeated-string-match/

func repeatedStringMatch(a string, b string) int {
	var times = len(b) / len(a) + 2 // 最大叠加次数
	var s = ""
	for i := 1; i <= times; i++ {
		s = s + a
		if isSub(s, b) {
			return i
		}
	}
	return -1
}

func isSub(str, target string) bool {
	var H = make([]int32, len(str)+1)
	for i := 1; i < len(H); i++ {
		H[i] = H[i-1] * b + int32(str[i-1] - 'a' + 1)
	}
	var targetH int32 = 0
	var p131 int32 = 1
	for i := range target {
		targetH = targetH * b + int32(target[i] - 'a' + 1)
		p131 = p131 * b
	}
	// H[r] - H[r-len(target)] * p131
	for r := len(target); r < len(H); r++ {
		if H[r] - H[r-len(target)] * p131 == targetH &&
			str[r-len(target):r] == target {
			return true
		}
	}
	return false
}

const b int32 = 131
const p int32 = 1e9 + 7